public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (0 == nums.length) {
            return new ArrayList<>();
        }
        Set<List<Integer>> rst = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 3; ++i) {
            for (int j = i + 1; j < nums.length - 2; j++) {
                int sub = target - (nums[i] + nums[j]);
                int k = j + 1, h = nums.length - 1;
                while (k < h) {                    
                    if (nums[k] + nums[h] == sub) {
                        ArrayList<Integer> tmp = new ArrayList<>();
                        tmp.add(nums[i]);
                        tmp.add(nums[j]);
                        tmp.add(nums[k]);
                        tmp.add(nums[h]);
                        rst.add(tmp);
                        while (k < h && nums[h] == nums[h-1]) {--h;}
                        while (k < h && nums[k] == nums[k+1]) {++k;}
                        ++k;
                        --h;
                    } else if (nums[k] + nums[h] > sub) {
                        --h;
                    } else {
                        ++k;
                    }
                }
            }
        }
        return new ArrayList<>(rst);
    }

}